package org.zxp.algorithm.sort;

import org.zxp.algorithm.sort.utils.Tools;

/**
 * @program: effectiveJava
 * @description: 快速排序
 * @author: X-Pacific zhang
 * @create: 2019-07-27 15:29
 **/
public class QuickSort {
    public static void main(String[] args) throws Exception {
        int[] sorts = {4,5,3,2,7,9,2,5};
        long time1 = System.currentTimeMillis();
        sorts = Tools.gen(10000000);
        long time2 = System.currentTimeMillis();
        QuickSort.quick_sort(sorts,0,sorts.length-1);
        long time3 = System.currentTimeMillis();
        Tools.printResult(sorts, time1, time2, time3,"快速");
//        Tools.print(sorts);
    }

    public static void quick_sort(int[] a, int p, int r){
        if(p>=r){
            return;
        }
        int q = QuickSort.partition(a,p,r);//获取一个点并获取此点的下标
        quick_sort(a,p,q-1);//对q点的前半段进行快排 q点相当于已经排好
        quick_sort(a,q+1,r);//队q点的后半段进行快拍
    }


    public static int partition(int[] a, int p, int r) {
        int i = p, j = p;//i-1为已经排好的范围，j为遍历的游标
        int pivot = a[r];//以最末尾的点为分界点
        while (true) {//并将大于此点的数据移动到右边，小于此点的数据移动到左边
            if (j == r) {//当遍历的游标到了数组末尾则把i的位置与末尾元素互换，并返回下标作为q点下标
                int tmp = a[i];
                a[i] = a[r];
                a[r] = tmp;
                return i;
            }
            if (a[j] <= pivot) {//如果小于末尾值，则i，j交换
                int tmp = a[i];
                a[i++] = a[j];
                a[j] = tmp;
            }//移动下标
            j++;
        }
    }
}
